package stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;

/**
 * @Author Fizz Pu
 * @Date 2021/5/6 下午8:41
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */


public class DanDiaoStack {
    public int[] nextDistance(int[] nums){
        if(nums == null){
            return null;
        }

        int len = nums.length;
        int[] rs = new int[len];
        Deque<Integer> stack = new ArrayDeque<>(len);
        for(int i = len - 1; i >= 0; i--){

            while (!stack.isEmpty() && nums[stack.getLast()] <= nums[i]){
                stack.removeLast();
            }

            if(stack.isEmpty()){
                rs[i] = 0;
            } else{
                rs[i] = stack.getLast() - i;
            }

            stack.addLast(i);
        }

        return rs;
    }

    public int[] nextCircleGreater(int[] nums){
        if(nums == null){
            return null;
        }

        int len = nums.length;
        int[] rs = new int[len];
        Deque<Integer> stack = new ArrayDeque<>(len);
        for(int i = len - 1; i >= 0; i--){
            int index = i;
            do{
                index = (index + 1) % len;


            }while (index == i);
        }

        return rs;
    }


    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        if(nums2 == null){
            return null;
        }

        int len2 = nums2.length;
        Deque<Integer> stack = new ArrayDeque<>(len2);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = len2 - 1; i >= 0; i--){

            while (!stack.isEmpty() && stack.getLast() <= nums2[i]){
                stack.removeLast();
            }

            if(stack.isEmpty()){
                map.put(nums2[i], -1);
            } else{
                map.put(nums2[i], stack.getLast());
            }

            stack.addLast(nums2[i]);
        }

        int len1 = nums1.length;
        int[] rs = new int[nums1.length];
        for(int i = 0; i < len1; i++){
            rs[i] = map.get(nums1[i]);
        }
        return rs;
    }

    public int[] nextGreater(int[] nums){
        // 1. 逆序遍历数组
        // 2. stack为空则push 结果数组为-1
        // 3. stack不为空, stack逐渐弹小于等于当前元素的元素, 则stack内所有元素大于当前元素.
        // 4. 如果stack为空, 结果数组置为-1,
        // 5. 否则置为stack顶部元素, 接着当前元素入stack

        if(nums == null){
            return null;
        }

        int len = nums.length;
        int[] rs = new int[len];
        Deque<Integer> stack = new ArrayDeque<>(len);
        for(int i = len - 1; i >= 0; i--){

            while (!stack.isEmpty() && stack.getLast() <= nums[i]){
                stack.removeLast();
            }

            if(stack.isEmpty()){
                rs[i] = -1;
            } else{
                rs[i] = stack.getLast();
            }

            stack.addLast(nums[i]);
        }

        return rs;
    }


    public static void main(String[] args) {
        DanDiaoStack stack = new DanDiaoStack();
        System.out.println(Arrays.toString(stack.nextDistance(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));

    }
}
